昨天寫了 prefix sum（前綴和），今天延續一下昨天的內容來看看差分。

差分基本上會和前綴和放在一起使用，大致概念就是打 tag，而且是一正一反、相互抵銷的兩個 tag（通常是 +1 和 -1），最後再用前綴和加總得到整個 array 的狀態。

拿 1109. Corporate Flight Bookings 這題來解釋應該很好懂，是區間加總題。這題會給定多個 input，例如 [1,3,10] 表示在第一到第三個位置都 +10，依此類推。

這題很輕鬆可以想出暴力解，直接創造出一個 array 然後把區間內所有位置都加上數字就好，不過會超時，因此需要用到差分和前綴和來優化。步驟如下：

1. 創造出一個 array
2. 對於 [start, end, cnt] 的 input
   • 在 array[start] 打上 +cnt 的 tag
   • 在 array[end+1] 打上 -cnt 的 tag
3. 用 prefix 對 array 做計算得到結果

這樣就結束啦。

因為 1109 之前做過了，所以今天寫的是 798. Smallest Rotation with Highest Score。其實去看解答和討論有更簡潔的寫法，只是我轉不過來，所以就用最基礎的差分寫法給大家參考。

另外提醒一下，寫這題記得要注意邊界條件，不然會被一直卡測資QQ

class Solution:
    def bestRotation(self, nums: List[int]) -> int:
        n = len(nums)
        arr = [0]*(n+1)

        for i in range(n):
            k = nums[i]
            if k == 0:
                arr[0] += 1
            elif i == n-1:
                arr[0] += 1
                arr[abs(n-1-k)+1] -= 1
            elif k == i:
                arr[0] += 1
                arr[1] -= 1
                arr[i+1] += 1
            elif k < i:
                arr[0] += 1
                arr[i-k+1] -= 1
                arr[i+1] += 1
            else:  # k > i
                arr[i+1] += 1
                arr[-(k-i-1+1)] -= 1

        for i in range(1, n):
            arr[i] += arr[i-1]
        
        mx = max(arr[:-1])

        return arr.index(mx)

差分題：

• 798. Smallest Rotation with Highest Score
• 2860. Happy Students
  • 隨手刷週賽結果就遇到相關題
  • 重點在於邊界的判斷，分組後組內人數／組內最大值／組外最小值的條件判斷

• Current count: 4
• 昨天寫基礎題太快樂結果今天稍微有變化就差點把自己繞死
• 距離小目標遙遙無期呢